﻿/*线性链表链式存储
 *
 */
#include "linkedlist.h"
#include <iostream>
#include <QThread>
#include <qdebug.h>
#include <stddef.h>
#include <malloc.h>
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

using namespace std;

//访问每个节点
void Visit(ElemType e){
    printf("%d ",e);
    //    fflush(stdout);
}
//头结点初始化
Status InitList(LinkList *L){
    *L=(LinkList)malloc(sizeof(Node));
    if((*L)==NULL)
        return -1;

    (*L)->next=NULL;
    (*L)->data=-1;

    return 0;
}
//是否为空
Status IsEmpty(LinkList L){
    if(L->next)
        return false;
    else
        return true;
}
//获取长度
int Length(LinkList L){
    int i=0;
    LinkList p=L->next;
    while(p){
        ++i;
        p=p->next;
    }
    return i;
}
//获取第i个元素的数据，e返回
bool GetElem(LinkList L,int i,ElemType *e){
    LinkList p=L->next;
    int j=1;

    while(j<i && p!=NULL)    {
        ++j;
        p=p->next;
    }
    if(j>i || p==NULL)
        return false;
    *e=p->data;
    return true;
}
//初始条件，线性表已经存在
//返回第一个与e值相同的节点的位置
int LocateElem(LinkList L,ElemType e){
    int i=0;
    LinkList p=L->next;

    while(p){
        ++i;
        if(p->data==e)
            return i;
        else
            p=p->next;
    }

    return -1;
}
//在第i个位置插入新数据
bool Insert(LinkList L,int i,ElemType e){
    int index=1;
    LinkList p=L;
    while(p && index<i){
        ++index;
        p=p->next;
    }
    if(p==NULL || index>i)
        return -1;
    LinkList newNode=(LinkList)malloc(sizeof(Node));
    if(newNode==NULL)
        return -1;
    newNode->data=e;
    newNode->next=p->next;
    p->next=newNode;

    return 0;
}
//删除第i个元素，用e返回其值
bool Delete(LinkList L,int i,ElemType *e){
    if(L==NULL)
        return false;


    int index=1;
    LinkList p=L;
    while(index<i && p->next!=NULL){
        ++index;
        p=p->next;
    }
    if(index>i || p==NULL)
        return false;

    //p指向第i-1个结点，p->next即为所求
    LinkList dNode=p->next;
    p->next=dNode->next;

    *e=dNode->data;
    free(dNode);

    return true;
}
//依次输出链表每个元素
int Display(LinkList L){
    printf("LinkedList:");
    if(L==NULL){
        printf("\n");
        fflush(stdout);
        return -1;
    }
    int  count=0;
#if 1
    LinkList p=L->next;
    while(p!=NULL){
        printf("%d ",p->data);
        p=p->next;

        ++count;
    }
    printf("\n");
#endif
    fflush(stdout);
    return count;
}
//头插法,创建n个元素
void CreateHead(LinkList L,int n){
    srand(time(NULL));
    LinkList p;

    for(int i=0;i<n;++i){
        p=(LinkList)malloc(sizeof(Node));
        if(p==NULL)
            return;

        p->data=rand()%100;
        p->next=L->next;

        L->next=p;
    }
}
//尾插法
void CreateTail(LinkList L,int n){
    srand(time(NULL));
    //pre指向最后一个结点
    LinkList pre=L;
    while(pre->next!=NULL)
        pre=pre->next;

    for(int i=0;i<n;++i){
        LinkList p=(LinkList)malloc(sizeof(Node));
        p->data=rand()%10;
        p->next=NULL;

        pre->next=p;
        pre=p;//r一直指向最后一个节点
    }
}
//销毁
int Destroty(LinkList *L){
    LinkList p;
    int count=0;

    while((*L)!=NULL){
        p=(*L);
        (*L)=(*L)->next;

        free(p);
        p=NULL;

        ++count;
    }
    qDebug()<<"成功销毁了结点数："<<count;
}

//
void LinkedBaseListTest(){
    qDebug()<<"----链表测试函数----";
#if 1
    LinkList L;
    InitList(&L);
    qDebug()<<"链表长度:"<<Length(L);

    qDebug()<<"----测试头插函数----";
    CreateHead(L,10);
    qDebug()<<"链表长度:"<<Length(L);
    Display(L);

    qDebug()<<"销毁了"<<Destroty(&L)<<"个结点";
    Display(L);

    qDebug()<<"----测试尾插法----";
    InitList(&L);
    qDebug()<<"链表长度:"<<Length(L);
    CreateTail(L,20);
    Display(L);

    qDebug()<<"销毁了"<<Destroty(&L)<<"个结点";
#endif
#if 0
    qDebug()<<"----测试指定位置插入----";
    InitList(&L);
    for(int i=1;i<=5;++i)
        Insert(L,1,i);

    Display(L);
    qDebug()<<"销毁了"<<Destroty(&L)<<"个结点";
#endif
    qDebug()<<"----测试读取指定位置----";
    InitList(&L);
    CreateHead(L,10);
    Display(L);

    ElemType *e=new ElemType;
    if(e==NULL)
        return;
    GetElem(L,5,e);
    qDebug()<<"第五个元素是："<<*e;

    qDebug()<<"----测试读取某元素的位置----";
    int loc=LocateElem(L,4);
    qDebug()<<"元素4的位置："<<LocateElem(L,4);
    qDebug()<<"元素2的位置："<<LocateElem(L,2);
    qDebug()<<"元素5的位置："<<LocateElem(L,5);

    qDebug()<<"----测试删除指定位置的元素----";
    Display(L);
    qDebug("删除第3个元素");
    Delete(L,3,e);
    Display(L);
    qDebug("删除第2个元素");
    Delete(L,2,e);
    Display(L);

    qDebug()<<"----链表测试函数结束----";
}


int Q1_find(LinkList L, const int k)
{
    if(L==NULL || k<0)
        return NULL;

    LinkList firstNode=L->next;
    LinkList secondNode=L->next;
    for(int i=0;i<k-1;++i){ //注意k-1
        if(firstNode->next!=NULL)
            firstNode=firstNode->next;
        else//当k超过链表的长度
            return NULL;
    }
    while(firstNode->next != NULL){
        firstNode=firstNode->next;
        secondNode=secondNode->next;
    }
    return secondNode->data;
}

void Q1_findTest()
{
    srand(time(NULL));
    LinkList  L=new LinkNode;
    L->next=NULL;
    CreateHead(L,10);
    Display(L);

    int result,k;
    k=rand()%10;
    result=Q1_find(L,k);
    printf("index:%d   result:%d",k,result);
    printf("\n");

    k=rand()%10;
    result=Q1_find(L,k);
    printf("index:%d   result:%d",k,result);
    printf("\n");

    k=rand()%10;
    result=Q1_find(L,k);
    printf("index:%d   result:%d",k,result);
    printf("\n");

    Destroty(&L);
}


void LinkedListOtherQuestionTest()
{
    /*1 输出链表中倒数第k个结点*/
    //    Q1_findTest();
    /*反转链表，输出链表所有元素*/
    //    Q2_reverseTest();
    //3 合并两个有序链表
    Q3MergeTest();
}

LinkList Q2_reverse(LinkList L)
{
    if(L==NULL)
        return NULL;

    LinkList first=L->next;
    LinkList second=NULL;
    LinkList forword=NULL;
    while(first!=NULL){
        forword=first->next;
        first->next=second;

        second=first;
        first=forword;
    }

    L->next=second;
    return L;
}

void Q2_reverseTest()
{
    srand(time(NULL));
    LinkList  L=new LinkNode;
    L->next=NULL;
    CreateHead(L,10);
    Display(L);

    L=Q2_reverse(L);
    Display(L);

    L=Q2_reverse(L);
    Display(L);

    Destroty(&L);
}

void Q3MergeTest()
{
    LinkList head1=new LinkNode;
    if(head1==NULL)
        return;
    head1->data=-1;
    CreatSortedLinkList(head1,10);
    Display(head1);
    qDebug()<<"head1 length:"<<Length(head1);

    QThread::msleep(1000);

    LinkList head2=new LinkNode;
    if(head2==NULL)
        return;
    head2->data=-1;
    CreatSortedLinkList(head2,10);
    Display(head2);
    qDebug()<<"head2 length:"<<Length(head2);

    qDebug()<<"Q3Merge--";
    LinkList mergedHead=Q3Merge(head1,head2);
    Display(mergedHead);

    //    Destroty(&head1);
    //    Destroty(&head2);
    Destroty(&mergedHead);
}

ListNode *Q3Merge(ListNode *pHead1, ListNode *pHead2)
{
    if(pHead1==NULL)
        return pHead2;
    if(pHead2==NULL)
        return pHead1;

    LinkList newHead,node1,node2,stepNode;
    node1=pHead1->next;
    node2=pHead2->next;

    newHead=pHead1;
    stepNode=newHead;
    if(node1->data <= node2->data){
        stepNode->next=node1;
        stepNode=stepNode->next;
        node1=node1->next;
    }
    else{
        stepNode->next=node2;
        stepNode=stepNode->next;
        node2=node2->next;
    }

    while(node1!=NULL && node2!=NULL){
        if(node1->data <= node2->data){
            stepNode->next=node1;

            stepNode=node1;
            node1=node1->next;
        }
        else{
            stepNode->next=node2;

            stepNode=node2;
            node2=node2->next;
        }
    }

    if(node1!=NULL)
        stepNode=node1;
    if(node2!=NULL)
        stepNode=node2;

    return newHead;
}

LinkList CreatSortedLinkList(LinkList L, int n)
{
    if(L==NULL || n<1)
        return NULL;

    srand(time(NULL));
    vector<int>intVtr;
    for(int i=0;i<n;++i)
        intVtr.push_back(rand()%100);

    sort(intVtr.begin(),intVtr.end(),less<int>());

    LinkList stepNode=L;
    for(int i=0;i<n;++i){
        LinkList  node=new LinkNode;
        if(node==NULL)
            return NULL;
        node->data=intVtr[i];
        node->next=NULL;

        stepNode->next=node;
        stepNode=node;
    }
    return L;
}

ListNode *Q4_Clone(ListNode *pHead)
{
    if(pHead==NULL)
        return NULL;
    //根据每个原结点制作一个克隆结点，放到原结点的后面
    ListNode *clone=NULL;
    ListNode *cur=pHead;
    while(cur!=NULL){
        clone=new ListNode;
        if(clone==NULL)
            return NULL;
        clone->data=cur->data;
        clone->next=cur->next;

        cur->next=clone;
        cur=clone->next;
    }
    //为克隆结点的random赋值A1->random=A->random->next;
    cur=pHead;
    while(cur->next!=NULL){
        clone=cur->next;
        clone->random=cur->random->next;

        cur=clone->next;
    }
    //拆分
    cur=pHead;
    ListNode*newListHead=cur->next;
    ListNode*tmp;
    while(cur->next!=NULL){
        clone=cur->next;

        tmp=clone->next;
        clone->next=cur->next;
        cur->next=tmp;

        cur=cur->next;
    }
    return newListHead;
}

void Q4_CloneTest()
{
#if 0
    LinkNode *head=CreatSortedLinkList_NoHead(10);
    Display_NoHead(head);

    LinkNode *newListHead=Q4_Clone(head);

    Destroty(&head);
    Destroty(&newListHead);
#endif
}

LinkList CreatSortedLinkList_NoHead(const int n)
{
    LinkNode *head=new LinkNode;
    CreatSortedLinkList(head,n);

    LinkNode *tmp=head;
    head=head->next;

    delete tmp;
    tmp=NULL;

    return head;
}

int Display_NoHead(LinkList L)
{
    ListNode *head=new ListNode;
    if(head==NULL)
        return -1;
    head->next=L;

    return Display(head);
}
